package leetcode.editor.vscdev.hot100;

import java.util.*;
import leetcode.editor.utils.*;

public class lc25_reverseKGroup {
    /* 反转k个一组链表 */
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode pre = dummy;
        ListNode end = dummy;

        while (end != null) {
            ListNode start = pre.next; // start指向k区间的开始
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;// 将end移到要反转的k区间末尾
            }
            if (end == null) {
                break;
            }
            ListNode next = end.next; // 下一次要进行反转的开始, 此处记录为了后续链接
            end.next = null; // 断开链表, 方便进行反转
            pre.next = reverse(start); // 反转的链表长度只有从start开始的k个, 后面断了
            start.next = next; // 反转后, start在k区间的尾部, 将其与原链表连接上
            pre = start; // 下次循环的开始, 就如初始化时pre和end都指向dummy
            end = pre;
        }
        return dummy.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;// 记录原本cur的下一个
            cur.next = pre; // cur.next变成之前的节点, 实现反转
            pre = cur; // pre指向cur位置, cur才可以移动到下一个
            cur = temp; // cur移动到原本的next, 进行下次处理
        }
        return pre; // 最后cur是null, pre就是反转后的头, 也就是处理的最后一个节点
    }
}
